package 中等.位运算;

/**
 * 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包
 * 含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。
 * 如果没有不包含相同字符的一对字符串，返回 0。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/aseY1I
 */
public class 单词长度的最大乘积_offer005 {

    public static void main(String[] args) {

        System.out.println(maxProduct2(new String[]{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"}));

    }

    /**
     * 模拟
     */
    public static int maxProduct(String[] words) {
        int max = 0;
        boolean[][] record = new boolean[words.length][26];
        for (int i = 0; i < record.length; i++) {
            boolean[] r = new boolean[26];
            for (char c : words[i].toCharArray()) {
                r[c - 'a'] = true;
            }
            record[i] = r;
        }

        for (int i = 0; i < record.length; i++) {
            boolean[] r1 = record[i];
            for (int j = i + 1; j < record.length; j++) {
                boolean hasLike = false;
                boolean[] r2 = record[j];
                for (int r = 0; r < r1.length; r++) {
                    if (r1[r] && r2[r]) {
                        hasLike = true;
                        break;
                    }
                }
                if (!hasLike) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }

        return max;
    }

    /**
     * 优化的关键在于快速判断两个字符串是否含有相同的字符
     * 由于只包含26个小写字母，可以用26个bit来记录该字符串
     * 是否包含某个字符，可以通过 bits1 & bits2 > 0 来判断
     * 是否有相同字符，将word转换为二进制用 |，因为word可能
     * 存在多个相同字符  110 | 010 == 110 不改变原数
     */
    public static int maxProduct2(String[] words) {
        int max = 0;
        int[] record = new int[words.length];
        for (int i = 0; i < record.length; i++) {
            int num = 0;
            for (char c : words[i].toCharArray()) {
                num |= 1 << (c - 'a');
            }
            record[i] = num;
        }

        for (int i = 0; i < record.length; i++) {
            for (int j = i + 1; j < record.length; j++) {
                if ((record[i] & record[j]) == 0) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }

        return max;
    }

}
